package demo10;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-13
 * Time: 22:28
 */
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
class Solution {
    public Node connect(Node root) {
        if(root==null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int sz = queue.size();
            while(sz>0){
                Node cur = queue.poll();
                if(sz-1!=0){
                    cur.next = queue.peek();
                }
                sz--;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
        }
        return root;
    }
}
class Solution1 {
    public Node connect(Node root) {
        if(root==null) return null;
        if(root.left!=null){
            root.left.next = root.right;
            if(root.next!=null){
                root.right.next = root.next.left;
            }
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}

//class Solution2 {
//    public boolean isCompleteTree(TreeNode root) {
//        if(root==null) return true;
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        boolean leaf = false;//是否遇到左右孩子不双全的节点
//        while(!queue.isEmpty()){
//            TreeNode cur = queue.poll();
//            TreeNode L = cur.left;
//            TreeNode R = cur.right;
//            //如果之前遇到过左右孩子不双全但是当前左右孩子节点不是叶子结点
//            if(leaf && (L!=null || R!=null) || (L==null&&R!=null)){
//                return false;
//            }
//            if(L!=null){
//                queue.offer(L);
//            }
//            if(R!=null){
//                queue.offer(R);
//            }
//            if(L==null||R==null){
//                leaf = true;
//            }
//        }
//        return true;
//    }
//}


/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
//class Solution4 {
//    public List<List<Integer>> levelOrder(Node root) {
//        List<List<Integer>> ret = new ArrayList<>();
//        if(root==null) return ret;
//        Queue<Node> queue = new LinkedList<>();
//        queue.offer(root);
//        while(!queue.isEmpty()){
//            int sz = queue.size();
//            List<Integer> list = new ArrayList<>();
//            for(int i =0;i<sz;++i){
//                Node cur = queue.poll();
//                list.add(cur.val);
//                //弹出一个节点把它的孩子全部都放到队列中
//                List<Node> child = cur.children;
//                for(Node x : child){
//                    queue.offer(x);
//                }
//            }
//            ret.add(list);
//        }
//        return ret;
//    }
//}
public class TestDemo {
    public static void main(String[] args) {

    }
}
